package linked_list

import (
	"errors"
	"fmt"
	"strings"
)

type tLinkedList struct {
	head *tLinkedNode
	tail *tLinkedNode
	size int
}

type tLinkedNode struct {
	value interface{}
	next *tLinkedNode
}

var gIndexOutofBoundsError = errors.New("index out of bounds")

func NewLinkedList() ILinkedList {
	return &tLinkedList{
		head: nil,
		tail: nil,
		size: 0,
	}
}

func newLinkedNode(value interface{}) *tLinkedNode {
	return &tLinkedNode{
		value,nil,
	}
}

func (me *tLinkedList) Size() int {
	return me.size
}

func (me *tLinkedList) IsEmpty() bool {
	return me.size <= 0
}

func (me *tLinkedList) IsNotEmpty() bool {
	return !me.IsEmpty()
}



func (me *tLinkedList) Get(i int) (error,interface{}) {
	e,_,node := me.getNodeAt(i)
	if e != nil {
		return e, nil
	}
	return e,node.value
}

func (me *tLinkedList) getNodeAt(i int) (err error, prev *tLinkedNode, node *tLinkedNode) {
	if i >= me.size || i < 0 {
		return gIndexOutofBoundsError, nil, nil
	}

	n := 0
	prev = nil
	node = me.head

	for {
		if n >= i {
			return nil, prev, node
		}

		if node == nil {
			return gIndexOutofBoundsError, nil, nil
		}

		n++
		prev = node
		node = node.next
	}
}

func (me *tLinkedList) Set(i int, value interface{}) error {
	e,prev,node := me.getNodeAt(i)
	if e != nil {
		return e
	}

	nn := newLinkedNode(value)

	if prev == nil {
		me.head = nn
	} else {
		prev.next = nn
	}

	nn.next = node.next
	if nn.next == nil {
		me.tail = nn
	}

	return nil
}

func (me *tLinkedList) Append(value interface{}) {
	nn := newLinkedNode(value)
	t := me.tail

	if t == nil {
		me.head = nn
	} else {
		t.next = nn
	}

	me.tail = nn
	me.size++
}

func (me *tLinkedList) Remove(i int) error {
	e,prev,node := me.getNodeAt(i)
	if e != nil {
		return e
	}

	if prev != nil {
		prev.next = node.next
	} else {
		me.head = node.next
	}

	if node.next == nil {
		me.tail = prev
	} else {
		me.tail = node.next
	}

	me.size--
	return nil
}

func (me *tLinkedList) Insert(i int, value interface{}) error {
	nn := newLinkedNode(value)

	if i == me.size {
		// always allow inserting tail
		t := me.tail
		me.tail = nn
		if t != nil {
			t.next = nn
		}

		if me.head == nil {
			me.head = nn
		}

		me.size++
		return nil
	}

	e,prev,node := me.getNodeAt(i)
	if e != nil {
		return e
	}

	if prev == nil {
		me.head = nn
	} else {
		prev.next = nn
	}
	nn.next = node

	me.size++
	return nil
}

func (me *tLinkedList) Iterator() IListIterator {
	items := make([]interface{}, me.size)
	i := 0
	for node := me.head;; {
		if node == nil {
			break
		}

		items[i] = node.value
		node = node.next
		i++
	}

	return newListIterator(items)
}

func (me *tLinkedList) String() string {
	items := make([]string, 0)

	if me.head == nil {
		items = append(items, "h=nil")
	} else {
		items = append(items, fmt.Sprintf("h=%v", me.head.value))
	}

	if me.tail == nil {
		items = append(items, "t=nil")
	} else {
		items = append(items, fmt.Sprintf("t=%v", me.tail.value))
	}

	items = append(items, fmt.Sprintf("s=%v", me.size))

	for node:=me.head;node != nil; {
		items = append(items, fmt.Sprintf("%v", node.value))
		node = node.next
	}

	return strings.Join(items, ",")
}